home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 7664 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.5 KB
  1. Path: keats.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: unique id for a string
  5. Date: 26 Feb 1996 06:46:09 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4gsh3hINNf3b@keats.ugrad.cs.ubc.ca>
  8. References: <1996Feb16.175601.114182@kuhub.cc.ukans.edu> <3129dd39.961626@news.iquest.net> <4gfpveINNe68@keats.ugrad.cs.ubc.ca> <4gih8a$b62@madeline.INS.CWRU.Edu>
  9. NNTP-Posting-Host: keats.ugrad.cs.ubc.ca
  10.  
  11. In article <4gih8a$b62@madeline.INS.CWRU.Edu>,
  12. Michael A. Balfour <mab22@po.CWRU.Edu> wrote:
  13.  >
  14.  >In a previous article, c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku) says:
  15.  >
  16.  >>In article <3129dd39.961626@news.iquest.net>,
  17.  >>Robert B. Clark <rclark@iquest.net> wrote:
  18.  >> >On 16 Feb 96 17:56:01 CST, anh@kuhub.cc.ukans.edu wrote:
  19.  >> >
  20.  >> >>HELLO =  H * 26^4 + E * 26 ^3 +  L * 26^2 + L * 26^1 + E * 26^0
  21.  >> >>
  22.  >> >>But the id is way too big. I need something that fits within a 32-bits int 
  23.  >> >>or a 64-bits long.
  24.  >> >
  25.  >> >You're thinking way too hard, perhaps.  Look up the algorithm for CRCs
  26.  >> >(cyclic redundancy checks/codes) in Snippets or most any other popular
  27.  >> >programmer's reference.
  28.  >>
  29.  >>But he wants a _unique_ ID. This is not possible, since the space of possible
  30.  >>words is much larger than the space of 32- or even 64-bit integers. Even for a
  31.  >>limited dictionary of around 200,000 words, a function that _guarantees_ a
  32.  >>unique hash for each indentifier into a 32-bit space is difficult to find.
  33.  >
  34.  >Actually, it's not *that* difficult to find.  Try running gperf from GNU
  35.  >or reading the paper cited in my previous post in this subject.  The
  36.  >results in the paper claim to be able to find a perfect hash function
  37.  >for 262,144 18-character words in 16.087 seconds on a Sun Sparc 2.
  38.  >Doesn't sound that difficult to me.  :)
  39.  >
  40.  >>One way to get a unique mapping is to simply assign increasing numbers to the
  41.  >>200,000+ words, and use a hashing technique to quickly look up a word given its
  42.  >>integer tag, and look up the tag given the word. With the proper
  43.  >>represenatation, both operations can be done in "constant time".
  44.  >
  45.  >Once again, using a perfect minimal hash function will provide an easy
  46.  >method for accomplishing this.
  47.  
  48. Definitely. But that assumes that the dictionary is not open to new members.
  49. Otherwise you have to recompute the hashing function each time you add a
  50. member. Does the paper discuss such ``loose ends''?
  51.  
  52. I am probably going to have a look at it, since perfect hashing functions are
  53. interesting things. :)
  54. -- 
  55.  
  56.